/*
	t[i][j] =  0     i = j
	           min{t[i][k] + t[k+][j] + w()}
*/
void minWeightTriang(int n, Elemtype **t, int **s)
{//t记录最权值，s记录对应的划分点
	for (int i = 0; i <= n; ++i)
	{
		t[i][i] = 0;
	}

	for (int r = 2; r <= n; ++r)
	{//当前链长,也就是子规模，r=2表示有三个点
		for (int i = 1; i<= n-r+1; i++)
		{//i为计算的前边界，当r为2时表示有三个点，{v0,v1,v2,v3,v4,v5,v6,v7}最大规模是8个点，i表示计算所有三个点的子规模的情况
			int j = i+r-1;//j表示后边界
			t[i][j] = t[i+1][j] + w(i-1,i,j);//选择以i为划分点
			s[i][j] = i;

			for (int k = i+1; k<j; k++)//选择最小划分点
			{
				int u = t[i][k] + t[k+1][j] + w(i-1,k,j);
				if(u < t[i][j])
				{
					t[i][j] = u;
					s[i][j] = k;
				}

			}
		}
	}
}
